class TreeNode:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


# 先序建立二叉树
def create_preorder():
    val = input('请输入节点元素值:')
    if val == '#':
        return
    node = TreeNode(val, create_preorder(), create_preorder())  # 创建节点
    return node


# 中序加后序建立二叉树输入提示
def create_inpost():
    inorder = []
    data = input("请输入中序遍历的结果:")
    while data != '#':
        inorder.append(data)
        data = input("请输入中序遍历的结果:")
    postorder = []
    data = input("请输入后序遍历的结果:")
    while data != '#':
        postorder.append(data)
        data = input("请输入后序遍历的结果:")
    return create_inorder_postorder(inorder, postorder)


# 中序加后序建立二叉树
def create_inorder_postorder(inorder, postorder):
    if len(postorder) == 0:
        return None
    # 创建当前节点
    data = postorder[-1]
    node = TreeNode(data)
    # 获取中序的根节点
    index = [i for i in range(len(inorder)) if inorder[i] == data][0]
    # 创建左子树
    node.left = create_inorder_postorder(inorder[0:index], postorder[: index])
    # 创建右子树
    node.right = create_inorder_postorder(inorder[index + 1:], postorder[index: -1])
    return node


# 层次建立二叉树
def create_level():
    print("请输入层次遍历的序列，如果节点为空则输入回车，输入#表示结束:")
    node_list = []
    data = input("请输入层次遍历的数据:")
    while data != "#":
        node_list.append(data)
        data = input("请输入层次遍历的数据:")

    if not node_list:
        return None
    # 创建头节点
    head = TreeNode(node_list[0])
    nodes = [head]
    i = 1
    for node in nodes:
        if node:
            node.left = (TreeNode(node_list[i]) if node_list[i] else None)
            nodes.append(node.left)
            i += 1
            if i == len(node_list):
                return head
            node.right = (TreeNode(node_list[i]) if node_list[i] else None)
            i += 1
            nodes.append(node.right)
            if i == len(node_list):
                return head


# 先序遍历二叉树
def preorder_traverse(head):
    if not head:
        return
    print(head.data, end='\t')  # 先访问根结点元素值
    preorder_traverse(head.left)
    preorder_traverse(head.right)


# 中序遍历二叉树
def inorder_traverse(head):
    if not head:
        return
    inorder_traverse(head.left)
    print(head.data, end='\t')  # 在中间位置访问根结点元素值
    inorder_traverse(head.right)


# 后序遍历二叉树
def postorder_traverse(head):
    if not head:
        return
    postorder_traverse(head.left)
    postorder_traverse(head.right)
    print(head.data, end='\t')  # 最后访问根结点元素值


# 层次遍历二叉树
def levelorder_traverse(head):
    queue = []  # 声明一个列表作为队列
    queue.append(head)  # 将根结点入队
    while queue:
        node = queue.pop(0)  # 出队一个节点
        print(node.data, end='\t')  # 输出节点元素值
        if node.left:
            queue.append(node.left)  # 若左孩子不为空，将左孩子入队
        if node.right:
            queue.append(node.right)  # 若右孩子不为空，将右孩子入队
